﻿using Common;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200717
    {
        //预先查看是否存在0
        //深度优先搜索：按照搜索树一直搜索，直到找到0或者无法继续搜索位置
        //广度优先搜索：按照搜索树一致搜索，直到队列中遇到0或者为空还没有找到0

        public bool CanReach(int[] arr, int start)
        {
            //数组中本身没有0的话则直接返回false
            if (!HasAValueByBinarySearch(arr,0,0,arr.Length-1))
                return false;
            //当前下标本身是0的话直接返回
            if (arr[start] == 0)
                return true;

            int[] status = new int[arr.Length];
            Queue<int> que = new Queue<int>();
            que.Enqueue(start);
            //start bfs
            while (que.Count>0)
            {
                int index = que.Dequeue();
                status[index] = 1;
                if (arr[index] == 0)
                    return true;

                int l = index - arr[index];
                int r = index + arr[index];
                if (l >= 0 && l < arr.Length && status[l] != 1)
                    que.Enqueue(l);
                if (r >= 0 && r < arr.Length && status[r] != 1)
                    que.Enqueue(r);              
            }

            return false;
        }

        public bool HasAValueByBinarySearch(int[] a, int goal, int startIndex, int endIndex)
        {
            if (startIndex <= endIndex)
            {
                int mid = (endIndex + startIndex) / 2;
                if (a[mid] == goal)
                    return true;

                return HasAValueByBinarySearch(a, goal, startIndex, mid - 1) || HasAValueByBinarySearch(a, goal, mid + 1, endIndex);
            }

            return false;

        }


    }
}
